Image points belonging to same feature are near each other. Parameter-space points belonging to same or similar features are near each other. Nearest neighbors can form point, line, or angle clusters {clustering algorithm}. Nearest-neighbor algorithms measure Euclidean distance, or other distance metrics, to find nearest-neighbor points and make clusters. Using distance measure can group features.
types
Clustering algorithms include hierarchical, self-organizing maps, K-means, fuzzy C-means, and expectation maximization. Error-weighted clustering retrofits clustering algorithms to use error-propagation information.
Self-organizing maps can group into equal categories.
process
Clustering can start with all features in one category and split features off {divisive clustering} or start with individual features and group them into classes {agglomerative clustering}. Clustering can use feature information to start or modify clustering {supervised clustering} or use only distances {unsupervised clustering}.
distance metric
Different hierarchical clustering methods use different ways to calculate distance between two clusters.
Minimum distance between cluster features {nearest-neighbor clustering} {single-linkage clustering} makes loose clusters with long branches containing few samples. Maximum distance between cluster features {furthest-neighbor clustering} {complete-linkage clustering} makes tight similar-size clusters with short branches.
Clustering can use average or median distance between features {unweighted pair-group method average} (UPGMA) or weighted-average point {centroid, cluster}.
For widely varying cluster sizes, average distance between features has weight {weighted pair-group average}: cluster feature number.
Clustering can use distance between cluster averages {within-groups clustering}.
distance metric: city-block distance
Distance measure between structure-space points is the same as Manhattan distance.
distance metric: Lp-metric
Distance measure between structure-space points is the same as Minkowski distance.
distance metric: Mahalanobis distance
Structure-space points have distances between them.
distance metric: Manhattan distance
Distance measure between structure-space points is the same as city-block distance.
distance metric: Minkowski distance
Distance measure between structure-space points is the same as Lp-metric.
supervised method
Classification can use already known patterns and clusters.
hierarchical clustering
Unsupervised, agglomerative clustering method {hierarchical clustering} measures distances between all points and places features in cluster hierarchy that looks like tree diagram {dendrogram, clustering}. Hierarchical clustering can make hierarchies and assign shared feature. Single features, and feature groups, are clusters. After calculating distance for cluster pairs, the closest clusters merge into one cluster, reducing cluster number by one. After calculating distance again for cluster pairs, the closest clusters merge into one cluster, and so on, until all features are in one, top-level cluster. Hierarchical clustering methods include centroid linkage, complete linkage, single linkage, and Ward's method. Ward's method calculates cluster mean and sum of squared differences from mean, for all cluster points. The next cluster is pair that gives smallest increase in sum of squared differences.
non-hierarchical clustering
Features can also be in different classes with no hierarchy {non-hierarchical clustering}.
non-hierarchical clustering: k-means clustering
Non-hierarchical, unsupervised method places features into a fixed number of clusters. First, it randomly assigns features to clusters. It calculates distances between feature pairs in cluster to find average cluster expression vector. It calculates distances between cluster pairs using average cluster expression vector. Features move to other clusters in turn, and method calculates all feature distances. Features stay in new cluster if distances between cluster feature pairs and between cluster pairs decrease.
Supervised k-means clustering first assigns features to clusters based on feature information and then proceeds as for unsupervised k-means clustering.
non-hierarchical clustering: self-organizing map
Non-hierarchical, unsupervised method places features in cluster based on nearness to cluster reference vector. First, cluster number is set. Starting from random vector, cluster reference vector converges by better partitioning feature data. It calculates distances between each expression vector and reference vectors and assigns feature to one cluster.
non-hierarchical clustering: principal component analysis
Non-hierarchical, unsupervised methods {principal component analysis, vision} (PCA) {singular value decomposition, vision} can combine feature dimensions linearly to reduce expression-space dimensions, remove redundancy, and average data. Similar unsupervised linear methods {factor analysis, computer} (FA) can look for significant factors in factor sets and find one, two, or three combined factors. It includes principal component analysis, correspondence analysis, spectral mapping, and non-linear mapping. Another similar technique {principal coordinate analysis} combines coordinates to make fewer dimensions. PCA, factor analysis, and principal coordinate analysis project data onto lower-dimension space by eliminating dimensions and dimension combinations with low significance. Number of remaining dimensions gives number of clusters to use for k-means clustering or self-organizing maps.
non-hierarchical clustering: support vector machine
Supervised clustering methods can use feature-vector training sets, group similar-function features into clusters, and group other-function features outside cluster. It tries to find cluster-specific features. Test features are in or outside cluster.
Features split space into two regions by making boundaries {hyperplane}. Hyperplanes can partition features so regions {soft margin} near hyperplanes have ambiguous examples.
Features can partition higher spaces {feature space}, mapped from feature vectors. Feature-space distances are metric and use special function {kernel function}. The best partition typically increases kernel function from simple to complex.
class analogy
Class analogy is a SIMCA method.
cluster sampling
Sampling can be from clusters equally.
cluster significance analysis
Using discrete or continuous data and embedded data can put compounds into groups by activity level. CSA locates small clusters in large spaces.
Cone and Hodgkin similarity index
Method measures molecular similarity.
discriminant-regression model
Model locates small clusters in large spaces.
distance-b program
Method locates small clusters in large spaces.
Jarvis-Patrick method
Structures can cluster in large databases by rating different features by similarity.
k-nearest neighbor
Supervised method calculates new object distance from all other objects to locate small clusters in large spaces.
partitioning
Process merges individuals into groups or splits whole into clusters.
similarity measure
Value can compare distances.
single-class discrimination
Method locates small clusters in large spaces.
Soft Independent Modeling of Class Analogies (SIMCA)
Supervised method uses model to find region boundaries or envelopes and locates small clusters in large spaces.
trend-vector analysis
Using activity and descriptor correlation vector ranks different features by similarity.
Image regions have sub-regions, which have different numbers of same-intensity pixels. Matrices can represent regions, and matrix cells can represent sub-regions. Cell values are number of same-intensity pixels. Matrices then have differences between cell sub-region values {Haar-like feature}, and matrices represent wavelets {Haar wavelet}. Regions are clusters or neighborhoods, such as rectangles or spheres, and so each region type has unique wavelet. Region sets have waves.
Images have points that do not cluster and do not belong to features. Outlier algorithms {outlier algorithms} use linear regression and best-fit to find outliers and discard them.
Methods {Potts model} can minimize energy by making two states either equal or unequal, with constant penalty for unequal and no penalty for equal.
3-Computer Science-Systems-Computer Vision-Algorithms
Outline of Knowledge Database Home Page
Description of Outline of Knowledge Database
Date Modified: 2022.0225